1. Technical Field
The present disclosure relates to optimizing Boolean logic. More particularly, the present disclosure relates to systems and methods for optimizing Boolean logic using organically-grown Karnaugh maps. The optimized Boolean logic is used to optimize digital circuits, design or program programmable logic devices, in cryptography, in formal logic analysis, and in software-based CAD programs or teaching programs.
2. Description of Related Art
Boolean algebra is useful for designing digital circuits because function variables map well to the discrete states of digital circuits. For example, the “true” and “false” values of Boolean variables are easily mapped to the digital circuit states of “1” and “0,” respectively. Additionally, Boolean algebra is useful in digital circuit design because digital circuits typically employ logic gates, including but not limited to, AND, NOT, NOR, and XOR. Well-known Boolean operators may represent these logic gates. For example, an AND gate is a circuit that physically operates as the logical conjunction operator of Boolean algebra. By using Boolean operators to represent these logic gates, Boolean algebra can be used to design, represent, and implement digital circuitry using function variables to represent the given status (or state) of a digital circuit.
Typically, the design of digital circuits begins by defining a set of desired output values to be produced by a set of input values. These output values can be conditioned upon previous input values or may be independent therefrom. Boolean variables are used to represent the input and output values. A Boolean expression is a function generated using Boolean variables and Boolean operators that completely represents the desired behavior of the digital circuit.
Once the Boolean expression is determined to characterize the digital circuit, the expression itself is converted to logic gates. These logic gates comprise several transistors using various well-known semiconductor design techniques, e.g., using photomasking techniques to implement the digital circuits using Complementary metal-oxide-semiconductor (“CMOS”) logic, Transistor-transistor logic (“TTL”), etc. However, redundancies within the semiconductor device may exist if care is not taken to ensure their preclusion. Specifically, the Boolean expression may have repeating terms and/or may unnecessarily require inputs that can safety be ignored without affecting the desired response of the digital circuit. Expressions containing repeating terms and/or unnecessary inputs lead to inefficiencies and increase the power consumption of the digital circuit.
Various software tools manipulate Boolean expressions to aid in the design of digital circuits. These software tools help optimize Boolean expressions which reduces the number of logic gates needed (e.g., less area of a semiconductor substrate is needed when used to implement the digital circuit), increases efficiency, and reduces the digital circuit's power consumption by reducing the number of digital logic elements needed to implement the digital circuit. These software tools employ various algorithms and techniques to facilitate manipulation of Boolean expressions by reducing the number input variables within the expression, by eliminating non-consequential input parameters. That is, Boolean variables typically have several minterms or implicants. These software tools identify minterms or implicants that can be combined to reduce the number of input variables needed. For example, a Karnaugh map (referred to herein as “K-map”) is used to optimize Boolean expressions by searching for minterms or maxterms that may be combined.
Additionally, Boolean expressions can be used in various other applications. For example, Boolean expressions may be used to design and program programmable logic devices, in cytological techniques, in formal logic analysis, and in software-based CAD programs or teaching programs.